/**
 * doubly sorted linked list
 * has to support the following operation efficiently<br>
 * 1. the entry with minimum time (nearestEvent pointer)<br>
 * 2. search and update multiple entries with the same oid of mo_from or mo_to <br>
 * 3.  add new entry <br>
 * 4. remove nearest  
 * @author Xiaohui
 * 
 */
package entity;

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class MyEventQSorted {
	MyEvent first;
	MyEvent last;
	int size;

	public MyEventQSorted() {
		first = null;
		last = null;
		size = 0;
	}

	public void add(int index, Object element) {
		MyEvent temp = (MyEvent) element;
		if (index == 0) {
			temp.next = first;
			first.previous = temp;
			first = temp;
		} else if (index == size - 1) {
			temp.previous = last;
			last.next = temp;
			last = temp;
		} else {
			int counter = 0;
			MyEvent e = first;
			while (counter < index) {
				e = e.next;
				counter++;
			}

			temp.previous = e.previous;
			temp.next = e;
			e.previous.next = temp;
			e.previous = temp;
		}

		size++;
	}

	/**
	 * TODO batch update, scan the list once
	 * 
	 * @param moid
	 * @param moid2OccTime
	 * @param from
	 */
	public void batUpdate(int moid, HashMap<Integer, Double> moid2OccTime,
			boolean from) {
		// MyEvent e = first;
		// if (from) {
		// // check first entry
		// if (e.mo_from.oid == moid
		// && moid2OccTime.keySet().contains(e.mo_to.oid)) {
		// double newOccTime = moid2OccTime.get(e.mo_to.oid);
		// e.timeToHappen = newOccTime;
		// if (newOccTime < nearestEvent.timeToHappen) {
		// nearestEvent = e;
		// }
		// } else {
		// if (e.mo_to.oid == moid
		// && moid2OccTime.keySet().contains(e.mo_from.oid)) {
		// double newOccTime = moid2OccTime.get(e.mo_from.oid);
		// e.timeToHappen = newOccTime;
		// if (newOccTime < nearestEvent.timeToHappen) {
		// nearestEvent = e;
		// }
		// }
		// }
		// e = e.next;
		// while (!e.equals(last)) {
		// if (e.mo_from.oid == moid
		// && moid2OccTime.keySet().contains(e.mo_to.oid)) {
		// double newOccTime = moid2OccTime.get(e.mo_to.oid);
		// e.timeToHappen = newOccTime;
		// if (newOccTime < nearestEvent.timeToHappen) {
		// nearestEvent = e;
		// }
		// }
		// e = e.next;
		// }
		// } else {
		// while (!e.equals(first)) {
		// if (e.mo_to.oid == moid
		// && moid2OccTime.keySet().contains(e.mo_from.oid)) {
		// double newOccTime = moid2OccTime.get(e.mo_from.oid);
		// e.timeToHappen = newOccTime;
		// if (newOccTime < nearestEvent.timeToHappen) {
		// nearestEvent = e;
		// }
		// }
		// e = e.next;
		// }
		// }
		// udpate size
		size += moid2OccTime.size();
	}

	public void clear() {
		first = null;
		last = null;
		size = 0;
	}

	/**
	 * delete the first elem
	 * 
	 * @return the nearest event
	 */
	public void delNearest() {
		first = first.next;
		first.previous = null;
		// update counter
		size--;
	}

	public MyEvent getFirst() {
		return this.first;

	}

	public MyEvent getLast() {
		return this.last;
	}

	public MyEvent getNearEvent() {
		return this.first;
	}

	/**
	 * Insert takes O(N)
	 * 
	 * @param newEvent
	 */
	public void insert(MyEvent newEvent) {
		if (isEmpty()) {
			last = newEvent;
			first = newEvent;
		} else {
			// if newEvent is same as one of the events in queue, update instead
			// of insert
			MyEvent e = first;
			while (e != null) {
				if (e.equals(newEvent)) {
					e.timeToHappen = newEvent.timeToHappen;
					break;
				}
				e = e.next;
			}
			//else
			if (e == null) {
				if (newEvent.timeToHappen <= first.timeToHappen) {
					insertFirst(newEvent);
				} else if (newEvent.timeToHappen >= last.timeToHappen) {
					insertLast(newEvent);
				} else {
					// linear search for the right pos
					e = first;
					while (e != null && e.timeToHappen <= newEvent.timeToHappen) {
						e = e.next;
					}
					// insert new event
					newEvent.previous = e.previous;
					newEvent.next = e;
					e.previous.next = newEvent;
					e.previous = newEvent;
				}
			}
		}

		// update counter
		size++;
	}

	private void insertFirst(MyEvent evn) {
		evn.next = first;
		first.previous = evn;
		first = evn;
	}

	private void insertLast(MyEvent newEvent) {
		newEvent.previous = last;
		last.next = newEvent;
		last = newEvent;
	}

	public boolean isEmpty() {
		return first == null;
	}

	/**
	 * @param event
	 * @return
	 */
	public void removeEvent(MyEvent event) {
		if (event.equals(first)) {
			first = first.next;
			first.previous = null;
			event.next = null;
		} else if (event.equals(last)) {
			last = last.previous;
			last.next = null;
			event.previous = null;
		} else {
			event.previous.next = event.next;
			event.next.previous = event.previous;
			event.previous = null;
			event.next = null;
		}
		size--;
	}

	/**
	 * @param oid
	 * @return list of events having mo_from oid == oid
	 */
	public LinkedList<MyEvent> removeWithFromID(int oid) {
		LinkedList<MyEvent> es = new LinkedList<MyEvent>();
		for (MyEvent e = first; e != null; e = e.next) {
			if (e.mo_from.oid == oid) {
				removeEvent(e);
				es.add(e);
			}
		}
		return es;
	}

	public int size() {
		return this.size;
	}

	public String toString() {
		String ret = "";
		MyEvent current = first; // start at beginning
		while (current != null) // until end of list,
		{
			ret += current.toString() + ", ";
			current = current.next; // move to next link
		}
		return ret;
	}

	/**
	 * update relevant entries
	 * 
	 * @param from_moid
	 * @param to_moid
	 * @param newOccTime
	 */
	public boolean update(int from_moid, int to_moid, double newOccTime) {
		System.out.println("updating: " + from_moid + " " + to_moid + " "
				+ newOccTime);
		MyEvent e = first;
		while (e != null) {
			if (e.mo_from.oid == from_moid && e.mo_to.oid == to_moid) {
				break;
			}
			e = e.next;
		}
		// System.out.println("e comes out");
		if (e == null) {
			// entry not found
			return false;
		}
		// delete e from q
		removeEvent(e);
		// insert e back to the q
		e.timeToHappen = newOccTime;
		insert(e);
		return true;
	}

}
